---
title: "10、平面切分"
created: 2025-11-28
tags:
  - 算法
---

# 10、平面切分

## 题目 [平面切分](https://www.lanqiao.cn/problems/503/learning/)

![[image-04e81264.png]]

## 思路分析

![[image-e63e6d84.png]]

有一种难叫做看着就难

但通过找规律可以发现

![[image-3cd387d0.png]]

每加一个线 必定会加一个面

另外 这条新加的线 每与之前的一条线有交点 就另加一个面（n个交点加n）

所以就是 想办法把线都存起来 —— {k,b} 因为这里直接给了a就是k b就是b 省事得多

然后加入线的时候 检查是否已经出现过

如果出现过 就不存在

如果没出现过 就加进去 然后加一个面

加进去之后 去与之前的所有线判断是否有交点 ——使用两点相交的公式

![[image-50b68ad6.png]]

注意交点会有可能重合 所以这里又需要一层set

## 代码实现

```cpp
#include<bits/stdc++.h>

using namespace std;

typedef pair<int,int> PII;

typedef pair<double,double> PDD;

set<PII> lines;

int IntersectPoint(set<PII> curlines,int k1,int b1){

  set<PDD> points;

  for(auto line:curlines){

    int k2=line.first,b2=line.second;

    if(k1!=k2){

      double x = (double)(b2 - b1) / (k1 - k2);

      //注意！！！右边要转变成double类型做计算 用(b2-b1)*1.0/(k1-k2)也行

      double y = k1 * x + b1;

      points.insert({x,y});

    }

  }

  return points.size();

}

int main()

{

  int n;cin>>n;

  int ans=1;

  while(n--){

    int k,b;

    cin>>k>>b;

    if(!lines.count({k,b})){

      ans++;

      ans+=IntersectPoint(lines,k,b);

      lines.insert({k,b});

    }

  }

  cout<<ans;

  return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[第六届 c++ B组 省赛|第六届 c++ B组 省赛]] 🏠 [[00-刷题理模型]] ➡️ [[1、字符排序|1、字符排序]]